篇首语：本文由编程笔记#小编为大家整理，主要介绍了为什么Java8中HashMap链表使用红黑树而不是AVL树相关的知识，希望对你有一定的参考价值。

在Jdk1.8版本后&＃xff0c;Java对HashMap做了改进&＃xff0c;在链表长度大于8的时候&＃xff0c;将后面的数据存在红黑树中&＃xff0c;以加快检索速度。

那么很多人就有疑问为什么是使用红黑树而不是AVL树&＃xff0c;AVL树是完全平衡二叉树阿&＃xff1f;

最主要的一点是&＃xff1a;

在CurrentHashMap中是加锁了的&＃xff0c;实际上是读写锁&＃xff0c;如果写冲突就会等待&＃xff0c;

如果插入时间过长必然等待时间更长&＃xff0c;而红黑树相对AVL树他的插入更快&＃xff01;

第一个问题为什么不一直使用树&＃xff1f;

参考《为什么HashMap包含LinkedList而不是AVL树&＃xff1f;》

我想这是内存占用与存储桶内查找复杂性之间的权衡。请记住&＃xff0c;大多数哈希函数将产生非常少的冲突&＃xff0c;因此为大小为3或4的桶维护树将是非常昂贵的&＃xff0c;没有充分的理由。

作为参考&＃xff0c;这是一个HashMap的Java 8 impl&＃xff08;它实际上有一个很好的解释&＃xff0c;整个事情如何工作&＃xff0c;以及为什么他们选择8和6&＃xff0c;作为“TREEIFY”和“UNTREEIFY”阈值&＃xff09;

第二个问题为什么hash冲突使用红黑树而不是AVL树呢

参考&＃xff1a;AVL树和红黑树之间有什么区别&＃xff1f;

红黑树和AVL树之间的区别

AVL树比红黑树保持更加严格的平衡。AVL树中从根到最深叶的路径最多为~1.44 lg&＃xff08;n &＃43; 2&＃xff09;&＃xff0c;而在红黑树中最多为~2 lg&＃xff08;n &＃43; 1&＃xff09;。

因此&＃xff0c;在AVL树中查找通常更快&＃xff0c;但这是以更多旋转操作导致更慢的插入和删除为代价的。因此&＃xff0c;如果您希望查找次数主导树的更新次数&＃xff0c;请使用AVL树。

AVL以及RedBlack树是高度平衡的树数据结构。它们非常相似&＃xff0c;真正的区别在于在任何添加/删除操作时完成的旋转操作次数。

两种实现都缩放为a O(lg N)&＃xff0c;其中N是叶子的数量&＃xff0c;但实际上AVL树在查找密集型任务上更快&＃xff1a;利用更好的平衡&＃xff0c;树遍历平均更短。另一方面&＃xff0c;插入和删除方面&＃xff0c;AVL树速度较慢&＃xff1a;需要更高的旋转次数才能在修改时正确地重新平衡数据结构。

对于通用实现&＃xff08;即先验并不清楚查找是否是操作的主要部分&＃xff09;&＃xff0c;RedBlack树是首选&＃xff1a;它们更容易实现&＃xff0c;并且在常见情况下更快 - 无论数据结构如何经常被搜索修改。一个例子&＃xff0c;TreeMap而TreeSet在Java中使用一个支持RedBlack树。

对于小数据&＃xff1a;

insert&＃xff1a;RB tree&＃xff06;avl tree具有恒定的最大旋转次数&＃xff0c;但RB树会更快&＃xff0c;因为平均RB树使用较少的旋转。

查找&＃xff1a;AVL树更快&＃xff0c;因为AVL树的深度较小。

删除&＃xff1a;RB树具有恒定的最大旋转次数&＃xff0c;但AVL树可以将O&＃xff08;log N&＃xff09;次旋转视为最差。并且平均而言&＃xff0c;RB树也具有较少的旋转次数&＃xff0c;因此RB树更快。

对于大数据&＃xff1a;

insert&＃xff1a;AVL树更快。因为您需要在插入之前查找特定节点。当您有更多数据时&＃xff0c;查找特定节点的时间差异与O&＃xff08;log N&＃xff09;成比例增长。但在最坏的情况下&＃xff0c;AVL树和RB树仍然只需要恒定的旋转次数。因此&＃xff0c;瓶颈将成为您查找该特定节点的时间。

查找&＃xff1a;AVL树更快。&＃xff08;与小数据情况相同&＃xff09;

删除&＃xff1a;AVL树平均速度更快&＃xff0c;但在最坏的情况下&＃xff0c;RB树更快。因为您还需要在删除之前查找非常深的节点以进行交换&＃xff08;类似于插入的原因&＃xff09;。平均而言&＃xff0c;两棵树都有恒定的旋转次数。但RB树有一个恒定的旋转上限。

--------------

 

参考&＃xff1a;AVL树与红黑树&＃xff1f;

在AVL树中&＃xff0c;从根到任何叶子的最短路径和最长路径之间的差异最多为1。在红黑树中&＃xff0c;差异可以是2倍。

这两个都给O&＃xff08;log n&＃xff09;查找&＃xff0c;但平衡AVL树可能需要O&＃xff08;log n&＃xff09;旋转&＃xff0c;而红黑树将需要最多两次旋转使其达到平衡&＃xff08;尽管可能需要检查O&＃xff08;log n&＃xff09;节点以确定旋转的位置&＃xff09;。旋转本身是O&＃xff08;1&＃xff09;操作&＃xff0c;因为你只是移动指针。

&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;

这里可以动态演示红黑树和AVL树以及其他数据结构和算法&＃xff0c;强烈推荐&＃xff1a;

https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

 

https://www.cs.usfca.edu/~galles/visualization/AVLtree.html